package graph;

import java.nio.channels.FileLock;
import java.util.*;

// 腐烂的橘子
public class leetcode994 {
    public static void main(String[] args) {
        int[][] nums = {{2,1,1},{0,1,1},{1,0,1}};
        System.out.print(orangesRotting(nums));
    }

    public static int orangesRotting(int[][] grid){
        int min = 0;
        int fresh = 0;
        boolean[][] flag = new boolean[grid.length][grid[0].length];
        Queue<int[]> queue = new LinkedList<>();
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 2){
                    int[] loc = {i,j};
                    queue.offer(loc);
                    flag[i][j] = true;
                }
                if(grid[i][j] == 1){
                    fresh++;
                }
            }
        }

        if(queue.isEmpty() && fresh == 0) return -1;
        if(queue.isEmpty() && fresh != 0) return 0;

        while(!queue.isEmpty()){
            Queue<int[]> temp = new LinkedList<>();
            while(!queue.isEmpty()){
                temp.offer(queue.poll());
            }
            while(!temp.isEmpty()){
                int[] loc = temp.poll();
                int i = loc[0];
                int j = loc[1];

                if( i-1 >=0 && grid[i-1][j] == 1 && flag[i-1][j] == false){
                    int[] t = {i-1, j};
                    flag[i-1][j] = true;
                    queue.offer(t);
                    fresh--;
                }
                if( j-1 >=0 && grid[i][j-1] == 1 && flag[i][j-1] == false){
                    int[] t = {i, j-1};
                    flag[i][j-1] = true;
                    queue.offer(t);
                    fresh--;
                }
                if( j+1 < grid[0].length && grid[i][j+1] == 1 && flag[i][j+1] == false){
                    int[] t = {i, j+1};
                    flag[i][j+1] = true;
                    queue.offer(t);
                    fresh--;
                }
                if( i+1 < grid.length && grid[i+1][j] == 1 && flag[i+1][j] == false){
                    int[] t = {i+1, j};
                    flag[i+1][j] = true;
                    queue.offer(t);
                    fresh--;
                }

            }
            min++;
        }

        return fresh==0? min-1:-1;
    }
}
